README.md

743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2 Output: 2 

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Solutions (Rust)

1. DFS

implSolution{pubfnnetwork_delay_time(times:Vec<Vec<i32>>,n:i32,k:i32) -> i32{letmut to_time = vec![vec![]; n asusize + 1];letmut stack = vec![k asusize];letmut min_time = vec![std::i32::MAX; n asusize + 1]; min_time[k asusize] = 0;for item in times { to_time[item[0]asusize].push((item[1]asusize, item[2]));}whileletSome(from) = stack.pop(){for i in0..to_time[from].len(){let(to, time) = to_time[from][i];if min_time[to] > min_time[from] + time { min_time[to] = min_time[from] + time; stack.push(to);}}}match min_time.into_iter().skip(1).max(){Some(std::i32::MAX) => -1,Some(t) => t, _ => -1,}}}